package com.jiang.专题.动态规划.Q1027;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/31 20:59
 */
class Solution {
    // 二维动态规划
    // public int longestArithSeqLength(int[] nums) {
    //     int res = 0;
    //     int[][] dp = new int[nums.length][1001]; // dp[i][j]表示第i个数减前面的数方差为j, dp[i][j]的值是方差为j的数列长度 - 1; 添加偏移量500保证非负
    //     for (int i = 0; i < nums.length; i++) {
    //         for (int j = 0; j < i; j++) {
    //             int variance = nums[i] - nums[j] + 500;
    //             dp[i][variance] = dp[j][variance] + 1;
    //             res = Math.max(dp[i][variance], res);
    //         }
    //     }
    //     return res + 1;
    // }

    // 一维动态规划
    public int longestArithSeqLength(int[] nums) {
        int maxValue = Arrays.stream(nums).max().getAsInt();
        int minValue = Arrays.stream(nums).min().getAsInt();
        int MaxVariance = maxValue - minValue;
        int res = 0;
        // 对所有可能得方差遍历
        for (int diff = -MaxVariance; diff <= MaxVariance; diff++) {
            int[] f = new int[maxValue + 1]; // 存放diff方差下，nums数组中的值能组成的最长数列
            Arrays.fill(f, -1);
            for (int num: nums) {
                int prebNum = num - diff; // num 减去方差，得到前一个数值
                if (prebNum <= maxValue && prebNum >= minValue && f[prebNum] != -1) {
                    f[num] = f[prebNum] + 1;
                    res = Math.max(res, f[num]);
                } else {
                    // 如果超过了最大最小值或者前一个数值的最长数列为-1，则num组成的最长数列为1
                    f[num] = 1;
                }
            }
        }
        return res;
    }
}
